import java.util.Arrays;

public class NM {
    //归并排序；
    public static void GuiBingPaiXu(int[] array){
        GuiBing(array,0,array.length-1);
    }
    public static void GuiBing(int[] array,int left,int right){
        //首先进行分成各个子组进行排序；
        //即进行分解操作；使用递归方法进行；
        if(left>=right){
            return;
        }
        int mid=(right+left)/2;
        GuiBing(array,left,mid);//进行左分解；
        GuiBing(array,mid+1,right);//进行右分解；
        //通过上述的分解完毕接着进行合并操作；
        HeBing(array,left,mid,right);//合并操作；
    }
    public static void HeBing(int[] array,int left,int mid ,int right){
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int s2=mid+1;
        while(s1<=mid&&s2<=right){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        // 处理左子数组剩余元素
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        // 处理右子数组剩余元素
        while (s2 <= right) {
            tmp[k++] = array[s2++];
        }

        for(int i=0;i<k;i++){
            array[i+left]=tmp[i];//此处的left作为一直归并操作的位置进行记录；
        }

    }
    public static void main(String[] args){
        int[] array={10,6,7,1,3,9,4,2};
        GuiBingPaiXu(array);
        System.out.println(Arrays.toString(array));
    }
}
